package acwing.算法题;/**
 * @author： li
 * @date： 2022-03-28 12:16
 * @version 1.0
 */

public class kmp {

/*
  对于任何字符串来说，前缀表的第一个字符作为单个字符串，没有前缀。
  前缀的表示有很多种，有的是将正常的下标统一左移，这里使用的是没有位移的原始坐标。
 */

    static void getNextArr(int[] next, String s) {
        int j = 0;//j表示前缀起始位置
        next[0] = 0;
        //i表示后缀起始位置
        for(int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }


    static int getIndexOf(String haystack, String needle) {
        if (haystack == null){
            return -1;
        }
        if (needle == null || needle.length() == 0) {
            return -1;
        }
        int[] next = new int[needle.length()];
        getNextArr(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while(j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length() ) {
                return (i - needle.length() + 1);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        
    }
}
